In recent years, researches in fields including communication fields such as the mobile-body communication and the deep-space communication as well as broadcasting fields such as the terrestrial wave broadcasting and the satellite digital broadcasting have been making very good progress. Accompanying these researches, studies of coding theories are also well conducted with the intention of increasing the efficiencies of error correction coding and error correction decoding.
A Shannon limit given by the so-called communication line coding theorem established by C. E. Shannon is known as a theoretical limit of coding performances. Studies of coding theories are conducted with the intention of developing codes demonstrating a performance close to the Shannon limit. In recent years, a technique known as the so-called turbo coding technique is being developed as a coding method demonstrating a performance close to the Shannon limit. The turbo coding technique is, for example, a coding technique such as PCCCs (Parallel Concatenated Convolutional Codes) and SCCCs (Serially Concatenated Convolutional Codes). While turbo codes are being developed, low density parity check codes are attracting a great deal of attention. Referred to hereafter as LDPC codes, the low density parity check codes are codes used in a coding method, which has been known since an early time in the past.
The LDPC codes were first proposed in a document authored by R. G. Gallager with a title of “Low Density Parity Check Codes,” as a document published by M. I. T. Press in the year of 1963 in Cambridge, Mass. Later on, the LDPC codes again drew lots of attention as described in documents such as a document authored by D. J. C. Mackay with a title of “Good error correcting codes based on very sparse matrices” as a document submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999 and a document authored by M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman with a title of “Analysis of low density codes and improved designs using irregular graphs” in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998.
Researches conducted in recent years are also clarifying the fact that, by increasing the code length of the LDPC codes, it is possible to display a performance close to the Shannon limit in the same way as the turbo codes or the like. In addition, the LDPC codes exhibit a property showing that the minimum distance is proportional to the code length. Thus, the LDPC codes offer merits that the LDPC codes have a good block error probability characteristic as one of its characteristics and the so-called error floor phenomenon hardly occurs in the LDPC codes. The error floor phenomenon is a phenomenon observed in decoding characteristics of the turbo codes or the like.
The LDPC codes are explained concretely as follows. It is to be noted that the LDPC codes are linear codes but are not necessarily 2-dimensional codes. In the following description, however, the LDPC codes are explained as 2-dimensional codes.
The most peculiar characteristic of the LDPC codes is the fact that a parity check matrix defining the LDPC codes is a sparse matrix. A sparse matrix is a matrix having a very small number of matrix elements each set at “1”. Let notation H denote a sparse parity check matrix. In this case, as shown in FIG. 1, a typical sparse matrix H has a humming weight of “3” for each column and a humming weight of “6” for each row.
LDPC codes defined by a parity check matrix H having a constant hamming weight for each row and a constant hamming weight for each column as described above are referred to as regular LDPC codes. On the other hand, LDPC codes defined by a parity check matrix H having a hamming weight varying from row to row and a hamming weight varying from column to column are referred to as irregular LDPC codes.
A LDPC-code encoding process is implemented to produce a generation matrix G on the basis of the parity check matrix H and generate code words by multiplying the generation matrix G by a 2-dimensional information message. To put it concretely, first of all, a coding apparatus for carrying out an LDPC-code encoding process finds a generation matrix G for which the equation GHT=0 holds true, where notation HT denotes the transposed matrix of the parity check matrix H. In this case, if the generation matrix G is a k×n matrix (that is, a matrix having k rows and n columns), the parity check matrix H is an (n−k)−row×n-column matrix.
If an n-bit code word c is an organization code matching a bit sequence including a k-bit information message u and (n−k) parity bits following the information message u for example, the (n−k)−row×n-column parity check matrix H includes an information portion and a parity portion. Associated with the k-bit information message u of the code word c having n bits, the information portion is a matrix portion having (n−k) rows and k columns. Associated with the (n−k) parity bits of the n-bit code word c, the parity portion is a matrix portion having (n−k) rows and (n−k) columns. In this case, if the parity portion is an upper triangular matrix or a lower triangular matrix, the process to code the information message u into LDPC codes can be carried out by making use of the parity check matrix H.
That is to say, for example, the parity check matrix H has an information portion and a parity portion, which is a lower triangle matrix as shown in FIG. 2. If all the elements of the lower triangle matrix of the parity portion are set at 1, the first one of the parity bits included in the code word c has a value obtained as a result of carrying out EXOR (exclusive logical sum) operations on elements each set at 1 on the first row of the information portion included in the parity check matrix H as a matrix portion associated with the information message u.
By the same token, the second one of the parity bits included in the code word c has a value obtained as a result of carrying out EXOR operations on elements each set at 1 on the second row of the information portion included in the parity check matrix H as a matrix portion associated with the information message u and the first one of the parity bits.
Likewise, the third one of the parity bits included in the code word c has a value obtained as a result of carrying out EXOR operations on elements each set at 1 on the third row of the information portion included in the parity check matrix H as a matrix portion associated with the information message u and the first and second ones of the parity bits.
Thereafter, similarly, the ith one of the parity bits included in the code word c has a value obtained as a result of carrying out EXOR operations on elements each set at 1 on the ith row of the information portion included in the parity check matrix H as a matrix portion associated with the information message u and first to (i−1)th ones of the parity bits.
The values of the (n−k) parity bits are found as described above, and the (n−k) parity bits are placed at a location following the information message u having k bits in order to create the code word having n bits.
A technique for decoding LDPC codes can be carried out by adoption of an algorithm proposed by Gallager as an algorithm referred to as a probabilistic decoding algorithm. The probabilistic decoding algorithm is a message passing algorithm based on belief propagation on the so-called Tanner graph including variable nodes also referred to as message nodes and check nodes. In the following description, the variable nodes and the check nodes may be properly referred to simply as nodes.
In a probabilistic decoding process, however, a message exchanged between nodes is a real number. Thus, in order to analyze the message, it is necessary to keep track of nothing but the probabilistic distribution of the message having a continuous value. That is to say, it is necessary to carry out an analysis entailing a very high level of difficulty. In order to solve this problem, Gallager proposed algorithms A and B as algorithms for decoding LDPC codes.
In general, a process for decoding LDPC codes is carried out in accordance with a procedure like one represented by a flowchart shown in FIG. 3. It is to be noted that, in the flowchart representing the procedure, notation Uo (uoi) denotes a received value, notation uj denotes a message output from a check node and notation vi denotes a message output from a variable node. In this case, a message is a real number expressing the “0” likelihood of a value in terms of the so-called log likelihood ratio. In addition, the log likelihood ratio expressing the “0” likelihood of the received value Uo is represented as received data uoi.
As shown in the flowchart of FIG. 3, the procedure for decoding LDPC codes begins with a step S11 at which a value Uo (uoi) is received. At the same step, a message uj and a variable k are initialized to 0. The variable k is used as a repetition processing counter taking an integer. Then, the flow of the procedure goes on to a step S12. At the step S12, a message vi is found in accordance with Eq. (1) based on the received value Uo (uoi). Then, a message uj is found in accordance with Eq. (2), which is based on the message vi.
                    [                  Eq          .                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                                                  ⁢                          u              j                                                          (        1        )                                [                  Eq          .                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Notation dv used in Eq. (1) denotes a parameter representing the number of elements arranged in the vertical direction (or the row arrangement direction) of the parity check matrix H as elements each set at “1”. On the other hand, notation dc used in Eq. (2) denotes a parameter representing the number of elements arranged in the horizontal direction (or the column arrangement direction) of the parity check matrix H as elements each set at “1”. The parameters dv and dc can be selected arbitrarily. In the case of a (3, 6) code for example, the parameter dv is set at 3 (or dv=3) whereas, the parameter dc is set at 6 (or dc=6).
It is to be noted that a message input from an edge for which a message is to be output is not used as an addition or multiplication parameter in the computation according to Eq. (1) or (2) respectively. Thus, the range of the summation operation according to Eq. (1) is from 1 to (dv−1) whereas the range of the multiplication operation according to Eq. (2) is from 1 to (dc−1). In addition, the multiplication operation according to Eq. (2) is actually carried out by creating a table showing values of a function R (v1, v2) expressed by Eq. (3) in advance and using the value of the function R continuously (or recursively) as shown in Eq. (4). The function R (v1, v2) has two inputs v1 and v2, generating one output as the value of the function.[Eq. 3]x=2 tan h−1[ tan h(v1/2)tan h(v2/2)]=R(v1,v2)  (3)[Eq. 4]uj=R(v1,R(v2,R(vdc-2,vdc-1))))  (4)
At the step S12, the variable k is also incremented by “1”. Then, the flow of the procedure goes on to a step S13. At the step S13, the variable k is compared with a repetitive-decoding count N determined in advance in order to produce a result of determination as to whether or not the variable k is at least equal to the repetitive-decoding count N. If the determination result produced in the process carried out at the step S13 indicates that the variable k is smaller than the repetitive-decoding count N, the flow of the procedure goes back to the step S12 in order to repeat the processes of the step S13 and the subsequent steps in the same way as before.
If the determination result produced in the process carried out at the step S13 indicates that the variable k is at least equal to the repetitive-decoding count N, on the other hand, the flow of the procedure goes on to a step S14 at which a process according to Eq. (5) is carried out in order to find and output a message v as an eventual output decoding result. Then, the execution of the procedure for decoding LDPC codes is ended.
                    [                  Eq          .                                          ⁢          5                ]                                                            v        =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                                                  ⁢                          u              j                                                          (        5        )            
The process according to Eq. (5) is different from the process according to Eq. (1) in that the process according to Eq. (5) is carried out by making use of input messages from all edges connected to the variable nodes.
In the case of a (3, 6) code for example, such a process for decoding LDPC codes is carried out by exchanging messages between nodes as shown in FIG. 4. In a node marked with the “=” special character as shown in FIG. 4 to indicate that the node is a variable node, a computation process according to Eq. (1) is carried out. In a node marked with the “+” to indicate that the node is a check node, on the other hand, a computation process according to Eq. (2) is carried out. Particularly, in accordance with the algorithm A, messages are each converted into a 2-dimensional message. In every node marked with the “+”, an exclusive logical summation process is carried out on (dc−1) input messages. In every node marked with the “=”, on the other hand, for a received value R, if (dv−1) input messages are all different bit values, the code is inverted before being output.
In addition, also in recent years, a method for implementing the technique for decoding LDPC codes is being studied as well. Before the method for implementing the technique for decoding LDPC codes is explained, first of all, modeling of the technique for decoding LDPC codes is described.
FIG. 5 is a diagram showing a typical parity check matrix H defining (3, 6) LDPC codes having a coding rate of ½ and a code length of 12. The parity check matrix H can be expressed by making use of a Tanner graph shown in FIG. 6. In the Tanner graph shown FIG. 6, a node marked with the “+” special character is a check node whereas a node marked with the “=” special character is a variable node. The check and variable nodes correspond respectively to the rows and the columns of the parity check matrix H. A line connecting a check node to a variable node is referred to as an edge corresponding to a matrix element set at “1” in the parity check matrix H. That is to say, if a matrix element located at the intersection of the jth row and the ith column in the parity check matrix H is set at 1, in the Tanner graph shown in FIG. 6, the ith variable node (or the ith node marked with the “=” special character) from the top of the graph is connected by an edge to the jth check node (or the jth node marked with the “+” special character) from the top of the graph. An edge connecting a check node to a variable node indicates that a coding bit for the variable node imposes a condition of constraint on the check node. It is to be noted that the Tanner graph shown in FIG. 6 is a Tanner graph drawn for the parity check matrix H shown in FIG. 5.
In accordance with a sum product algorithm adopted as an algorithm of the method for decoding LDPC codes, variable-node and check-node computation processes are carried out repeatedly.
In a variable node, the computation according to Eq. (1) is carried out as shown in FIG. 7. That is to say, as shown in FIG. 7, a message vi for an edge serving as the object of message computation is computed by making use of messages u1 and u2 from remaining edges each connected to the variable node as well as received information uoi. Messages for other edges are computed in the same way.
Before the check-node computation process is explained, Eq. (2) is rewritten into Eq. (6) given below by making use of the equation a×b=exp{ ln(|a|)+ln(|b|)}×sign (a)×sign (b) where sign (x) has a value of 1 for x≧0 and a value of −1 for x<0.
                    [                  Eq          .                                          ⁢          6                ]                                                                      u          j                =                              2            ⁢                                          tanh                                  -                  1                                            ⁡                              (                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      tanh                    ⁡                                          (                                                                        v                          i                                                2                                            )                                                                      )                                              ⁢                                          ⁢                                          =                                    2              ⁢                                                tanh                                      -                    1                                                  ⁡                                  [                                      exp                    ⁢                                          {                                                                        ∑                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  ln                          ⁡                                                      (                                                                                                                        tanh                                ⁡                                                                  (                                                                                                            v                                      i                                                                        2                                                                    )                                                                                                                                                    )                                                                                              }                                        ×                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              sign                        ⁢                                                                                                  ⁢                                                  (                                                      tanh                            ⁡                                                          (                                                                                                v                                  i                                                                2                                                            )                                                                                )                                                                                                      ]                                                      ⁢                                                  ⁢                                                  =                          2              ⁢                                                tanh                                      -                    1                                                  ⁡                                  [                                      exp                    ⁢                                          {                                              -                                                  (                                                                                    ∑                                                              i                                =                                1                                                                                                                              d                                  c                                                                -                                1                                                                                      ⁢                                                          -                                                              ln                                ⁡                                                                  (                                                                      tanh                                    ⁡                                                                          (                                                                                                                                                                                                              v                                            i                                                                                                                                                                    2                                                                            )                                                                                                        )                                                                                                                                              )                                                                    }                                                        ]                                            ×                                                ∏                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  sign                  ⁢                                                                          ⁢                                      (                                          v                      i                                        )                                                                                                          (        6        )            
In addition, if the equation φ(x)=ln(tan h(x/2)) is defined for x≧0, the equation φ−1(x)=2 tan h−1(e−x) holds true. Thus, Eq. (6) can be rewritten into Eq. (7) given as follows.
                    [                  Eq          .                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁢                                                          ⁢                              (                                  v                  i                                )                                                                        (        7        )            
In a check node, the computation according to Eq. (7) is carried out as shown in FIG. 8. That is to say, as shown in FIG. 8, a message uj for an edge serving as the object of message computation is computed by making use of messages v1, v2, v3, v4 and v5 from remaining edges each connected to the check node. Messages for other edges are computed in the same way.
It is to be noted that the function φ(x) can also be expressed by the equation φ(x)=ln((ex+1)/(ex−1)). Thus, the equation φ(x)=φ−1(x) holds true for x>0. If the functions φ(x) and φ−1(x) are implemented by hardware, the functions may be realized by making use of a LUT (Look Up Table) in some cases. In these cases, the same LUT common to both the functions is used.
If the sum product algorithm is implemented by making use of hardware, the variable-node computation according to Eq. (1) and the check-node computation according to Eq. (7) need to be carried out repeatedly by making use of a proper circuit scale and at a proper operating frequency.
First of all, the following description explains an implementation method adopted in a decoding process. In accordance with the implementation method, computations at nodes are simply carried out sequentially one computation after another in order to perform a decoding process.
It is to be noted that, in this case, let a decoding process be carried out in order to decode codes expressed by a parity check matrix H having 36 (rows)×108 (columns) as shown in FIG. 9 as codes having a coding rate of ⅔ and a code length of 108. The number of matrix elements each set at 1 in the parity check matrix H is 323. Thus, the number of edges in the Tanner graph representing the parity check matrix H is also 323. In the parity check matrix H shown in FIG. 9, matrix elements reset to 0 are each represented by the period “.”.
FIG. 10 is a diagram showing a decoding apparatus for carrying out a process of decoding LDPC codes once.
In the decoding apparatus shown in FIG. 10, for every operating clock, a message for 1 edge is computed.
That is, the decoding apparatus shown in FIG. 10 is provided with two edge memories 100 and 102, a check-node computer 101, a variable-node computer 103, a reception memory 104 and a control section 105.
In the decoding apparatus shown in FIG. 10, message data are read out from the edge memory 100 or 102 sequentially one message after another. Then, a message for an edge serving as an object of message computation is computed by making use of the messages read out from the edge memory 100 or 102. Subsequently, the messages computed for the edge serving as an object of message computation are stored in the edge memory 102 or 100 provided at a stage following the edge memory 100 or 102 respectively sequentially one message after another. In order to carry out this decoding process repeatedly, a plurality of decoding apparatus each like the one shown in FIG. 10 as a decoding apparatus for carrying out a process of decoding LDPC codes once are connected to each other in a cascade configuration. As an alternative, the decoding apparatus shown in FIG. 10 is used repeatedly in order to carry out the decoding process repeatedly. It is to be noted that, in the following description, as an example, a plurality of decoding apparatus each like the one shown in FIG. 10 as a decoding apparatus for carrying out a process of decoding LDPC codes once are connected to each other in a cascade configuration.
The edge memory 100 is used for storing messages D100 each received from a variable-node computer 103 employed in a decoding apparatus provided at the immediately preceding stage not shown in the figure in an order the check-node computer 101 provided at the stage following the edge memory 100 reads out the messages D100. Then, at a check-node computation phase, the messages D100 are read out from the edge memory 100 and supplied to the edge memory 100 as messages D101 in the order the messages D100 were stored in the edge memory 100.
On the basis of a control signal D106 received from the control section 105, the check-node computer 101 carries out the computation process according to Eq. (7) by making use of the messages D101 in order to generate a message D102, and supplies the message D102 to the edge memory 102 provided at a stage immediately following the check-node computer 101.
The edge memory 102 is used for storing messages D102 received from the check-node computer 101 provided at the immediately preceding stage in an order the variable-node computer 103 provided at the stage immediately following the edge memory 102 reads out the messages D100. Then, at a variable-node computation phase, the messages D102 are read out from the edge memory 102 and supplied to the variable-node computer 103 as messages D103 in the order the messages D102 were stored in the edge memory 102.
In addition, the variable-node computer 103 also receives a control signal D107 from the control section 105 and received data D104 from the reception memory 104. On the basis of the control signal D107, the variable-node computer 103 carries out the computation process according to Eq. (1) by making use of the message D103 received from the edge memory 100 and the received data D104 received from the reception memory 100 in order to produce a message D105 as a result of the computation process, and supplies the message D105 to an edge memory 100 employed in a decoding apparatus provided at the immediately following stage not shown in the figure.
The reception memory 104 is used for storing LDPC codes, which are received data already converted into LDPC codes. The control section 105 supplies the control signal D106 to the check-node computer 101 as a signal for controlling the check-node computation process. By the same token, the control section 105 supplies the control signal D107 to the variable-node computer 103 as a signal for controlling the variable-node computation process. The control section 105 supplies the control signal D106 to the check-node computer 101 when messages received from all edges have been stored in the edge memory 100. By the same token, the control section 105 supplies the control signal D107 to the variable-node computer 103 when messages received from all edges have been stored in the edge memory 102.
FIG. 11 is a block diagram showing a typical configuration of the check-node computer 101 employed in the decoding apparatus shown in FIG. 10 as a check-node computer 101 for carrying out check-node computation processes sequentially one process after another.
It is to be noted that, in the configuration shown in FIG. 11 as the configuration of the check-node computer 101, each message is quantized into a total of 6 bits including a sign bit. In addition, in the configuration shown in FIG. 11, a check-node computation process is carried out on LDPC codes defined by the parity check matrix H shown in FIG. 9. Moreover, the check-node computer 101 shown in FIG. 11 receives a clock signal ck providing the necessary clock signal ck to the check-node computer 101. Thus, each block employed in the check-node computer 101 carries out an operation synchronously with the clock signal ck.
On the basis of the control signal D106 received from the control section 105 as a control signal including typically 1 bit, the check-node computer 101 shown in FIG. 11 carries out the computation process according to Eq. (7) by making use of messages D101 sequentially read out from the edge memory 100 one message after another.
That is to say, the check-node computer 101 reads out 6-bit messages D101 (or messages vi) each received from a variable node corresponding to a column of the parity check matrix H sequentially one message after another, supplying the less significant bits included in the message as bits representing an absolute value D122 (|vi|) of the message to a LUT 121 and the most significant bit D121 included in the message as a bit representing the sign of the message to an EXOR circuit 129 and a FIFO (First In First Out) memory 133. In the check-node computer 101, the control signal D106 received from the control section 105 is supplied to selectors 124 and 131.
For the absolute value D122 (|vi|) supplied to the LUT 121, the LUT 121 reads out 5-bit data D123 (φ(|vi|) used in the computation process according to Eq. (7)) and supplies the data D123 (φ(|vi|)) to an adder 122 and a FIFO memory 127.
The adder 122 adds the data D123 (φ(|vi|)) to 9-bit data D124 stored in a register 123 and stores back the cumulative sum including 9 bits in the register 123 as new 9-bit data D124 replacing the previous data D124 also including 9 bits. It is to be noted that, when the process to find the cumulative sum has been completed for the absolute values D122 (|vi|) of messages D101 received from all the edges along 1 row of the parity check matrix H, the register 123 is reset.
When messages D101 received from all the edges along 1 row of the parity check matrix H are read out sequentially one message after another and the final cumulative sum representing the sum of function values D123 along the row is stored in the register 123, the control section 105 changes the control signal D106 supplied thereby from 0 to 1. For a row weight of 9 for example, the control signal D106 stays at 0 during a period covering the first to eighth clock pulses. As the ninth clock pulse is generated, the control section 105 changes the control signal D106 from 0 to 1.
With the control signal D106 set at 1, a selector 124 selects the cumulative sum D124 stored in the register 123 and supplies the cumulative sum D124 to a register 125 as data D125 to be stored in the register 125. The cumulative sum D124 stored in the register 123 with the control signal D106 set at 1 is a 9-bit value obtained as a result of cumulatively adding the function values D123 (or φ(|vi|)) obtained for messages D101 (or messages vi) received from all the edges along 1 row of the parity check matrix H. That is to say, the cumulative sum D124 stored in the register 123 with the control signal D106 set at 1 is the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=dc. The data D125 stored in the register 125 is supplied to the selector 124 and an adder 126 as data D126 including 9 bits. With the control signal D106 reset at 0, on the other hand, the selector 124 selects the 9-bit data D126 received from the register 125 and outputs the selected data D126 including 9 bits to the register 125 as data to be stored in the register 125 again. That is to say, the register 125 supplies a cumulative value obtained previously as the 9-bit cumulative sum of the function values φ(|vi|) to the selector 124 and the adder 126 till data including 9 bits is obtained as a result of cumulatively adding the function values φ(|vi|) obtained for messages D101 (or messages vi) received from all the edges along 1 row of the parity check matrix H.
On the other hand, the FIFO memory 127 delays the data D123 (φ(|vi|)) output by the LUT 121 to a point of time at which the register 125 supplies new data D126 (Σφ(|vi|) for a summation range starting from i=1 and ending at i=dc) to the adder 126. Then, the FIFO memory 127 supplies the data D123 to an adder 126 as data D127 including 5 bits. The adder 126 subtracts the data D127 supplied by the FIFO memory 127 from the data D126 supplied by the register 125 and supplies the difference to an LUT 128 as difference data D128 including 5 bits. That is to say, the adder 126 subtracts the 5-bit function value φ(|vi|) found for a message D101 (or a message vi) received from an edge serving as an object of message computation from 9-bit data obtained as a result of cumulatively adding the function values φ(|vi|) obtained for messages D101 (or messages vi) received from all the edges along 1 row of the parity check matrix H, and supplies the difference to an LUT 128 as the difference data D128 including 5 bits. The difference data D128 is thus the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=(dc−1).
It is to be noted that, even though the adder 126 subtracts the 5-bit data D127 supplied by the FIFO memory 127 from the 9-bit data D126 supplied by the register 125 to result in a difference including up to 9 bits, the adder 126 supplies difference data D128 including 5 bits. In consequence, if the adder 126 subtracts the 5-bit data D127 supplied by the FIFO memory 127 from the 9-bit data D126 supplied by the register 125 to result in a difference, that cannot be expressed by 5 bits, that is, if the adder 126 produces a difference greater than 31 (or 11111 if represented in the binary format), which is the maximum value of data including 5 bits, the adder 126 clips the difference to the maximum value of 31 and supplies the maximum value as the difference data D128 including 5 bits.
For the difference data D128, which is the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=(dc−1), the LUT 128 reads out 5-bit data D129 (φ−1(Σφ(|vi|)) used in the computation process according to Eq. (7)).
Concurrently with the processing described above, the EXOR circuit 129 computes the exclusive logical sum of 1-bit data D131 stored in a register 130 and the sign bit D121. That is to say, the EXOR circuit 129 computes the product of two sign bits. The multiplication result D130 including 1 bit is stored back in the register 130. It is to be noted that, when the sign bits D121 extracted from messages D101 received from all the edges along 1 row of the parity check matrix H have been subjected to the multiplication process carried out by the EXOR circuit 129, the contents of the register 130 are reset.
When the multiplication result D130 (Πsign (vi) from i=1 and ending at i=dc) obtained from the multiplication processes carried out on the sign bits D121 extracted from messages D101 received from all the edges along 1 row of the parity check matrix H is stored in the register 130, the control section 105 changes the control signal D106 supplied thereby from 1 to 0.
With the control signal D106 set at 1, a selector 131 selects the multiplication result D131 stored in the register 130 and supplies the multiplication result D131 to a register 132 as 1-bit data 132 to be stored in the register 132. As described above, the multiplication result D131 stored in the register 130 with the control signal D106 set at 1 is a 1-bit data obtained as a result of the multiplication processes on the sign bits D121 extracted from messages D101 received from all the edges along 1 row of the parity check matrix H. That is to say, the multiplication result D131 stored in the register 130 with the control signal D106 set at 1 is the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=dc. The data D132 stored in the register 132 is supplied to the selector 131 and an EXOR circuit 134 as data D133 including 1 bit. With the control signal D106 reset at 0, on the other hand, the selector 131 selects the 1-bit data D133 received from the register 132 and outputs the selected data D133 including 1 bit to the register 132 as data to be stored in the register 132 again. That is to say, the register 132 supplies the data D133 already stored therein to the EXOR circuit 134 and the selector 131 till data including 1 bit is obtained as a result of the multiplication processes carried out by the EXOR circuit 129 on the sign bits D121 extracted from messages D101 (or messages vi) received from all the edges along 1 row of the parity check matrix H.
On the other hand, the FIFO memory 133 delays the sign bit D121 to a point of time at which the register 132 supplies new data D133 (or the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=dc) to the EXOR circuit 134. Then, the FIFO memory 133 supplies the delayed sign bit D121 to the EXOR circuit 134 as data D134 including 1 bit. The EXOR circuit 134 computes an exclusive logical sum of the data D133 received from the register 132 and the 1-bit data D134 received from the FIFO memory 133 in order to divide the data D133 by the data D134 including 1 bit, producing a division result also including 1 bit. Then, the EXOR circuit 134 outputs the division result including 1 bit as data D135. That is to say, the EXOR circuit 134 divides a product of sign bits D121 (sign (|vi|)) extracted from messages D101 received from all the edges along 1 row of the parity check matrix H by the sign bit D121 (sign (|vi|)) extracted from a message D101 (or a message vi) received from an edge serving as an object of message computation, and outputs the division result (or the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=(dc−1)) as the division result D135.
The check-node computer 101 concatenates the 5-bit processing result D129 generated by the LUT 128 with the 1-bit division result D135 produced by the EXOR circuit 134 by taking the processing result D129 including 5 bits as 5 less significant bits and the division result D135 including 1 bit as the most significant bit in order to output a message D102 (or a message uj) including a total of 6 bits.
As described above, the check-node computer 101 carries out the computation processing according to Eq. (7) in order to find a message uj.
It is to be noted that, since the maximum value of the row weight for the parity check matrix H shown in FIG. 9 is nine, that is, since the maximum number of messages supplied to the check node is nine, the check-node computer 101 is provided with the FIFO memory 127 and the FIFO memory 133, which are used for delaying the nine messages (or the value of the function φ(|vi|)). In a process to handle row messages fewer than the row weight of 9, the magnitude of the delay provided by the FIFO memory 127 and the FIFO memory 133 can be reduced to a value corresponding to the row weight for the processed row messages.
FIG. 12 is a block diagram showing a typical configuration of the variable-node computer 103 included in the decoding apparatus shown in FIG. 10 as a variable-node computer 103 for carrying out variable-node computation processes sequentially one process after another.
It is to be noted that, in the configuration shown in FIG. 12 as a typical configuration of the variable-node computer 103, each message is quantized into a total of 6 bits including a sign bit. In addition, in the configuration shown in FIG. 12, a variable-node computation process is carried out on LDPC codes expressed by the parity check matrix H shown in FIG. 9. On top of that, the variable-node computer 103 shown in FIG. 12 receives a clock signal ck providing the necessary clock signal ck to the variable-node computer 103. Thus, each block employed in the variable-node computer 103 carries out an operation synchronously with the clock signal ck.
On the basis of the control signal D107 received from the control section 105 as a control signal having typically 1 bit, the variable-node computer 103 shown in FIG. 12 carries out the computation process according to Eq. (1) by making use of messages D103 sequentially read out from the edge memory 102 one message after another and received data D104 read out from the reception memory 104.
That is to say, the variable-node computer 103 reads out 6-bit messages D103 (or messages uj) each received from a check node corresponding to a row of the parity check matrix H sequentially one message after another, supplying the messages D103 to an adder 151 and a FIFO memory 155. In addition, the variable-node computer 103 reads out pieces of received D104 including 6 bits from the reception memory 104 sequentially one piece after another, supplying the pieces of received including 6 bits to an adder 156. The variable-node computer 103 supplies a control signal D107 received from the control section 105 to a selector 153.
The adder 151 adds the message D103 (or the message uj) to 9-bit data D151 stored in a register 152 in order to produce a cumulative message D103 including 9 bits and stores the cumulative message D103 also including 9 bits also in the register 152. It is to be noted that, after the messages D103 received from all the edges along one column of the parity check matrix H are cumulatively added and stored in the register 152, the contents of the register 152 are reset.
After the variable-node computer 103 reads out messages D103 received from all edges along a column of the parity check matrix H sequentially one message after another and the adder 151 adds the message D103 in order to produce a cumulative message D103 including 9 bits and stores the cumulative message D103 also including 9 bits also in the register 152, the control section 105 changes the control signal D107 supplied thereby from 0 to 1. In the case of a column weight of 5 for example, the control signal D107 stays at 0 during a period covering the first to fourth clock pulses. As the fifth clock pulse is generated, the control section 105 changes the control signal D107 from 0 to 1.
With the control signal D107 set at 1, a selector 153 selects the 9-bit cumulative sum D151 stored in the register 152 and supplies the selected cumulative sum D151 to a register 154 to be stored in the register 154. The cumulative sum D151 stored in the register 152 set at 1 is a 9-bit value obtained as a result of cumulatively adding the messages D103 (or messages uj) received from all the edges along 1 column of the parity check matrix H. That is to say, the cumulative sum D151 stored in the register 152 set at 1 is the value of Σuj for a summation range starting from j=1 and ending at j=dv. The data D151 stored in the register 154 is supplied to the selector 153 and an adder 156 as data D152 consisting of 9 bits. With the control signal D107 reset at 0, on the other hand, the selector 153 selects the 9-bit data D152 received from the register 154 and outputs the selected data D152 including 9 bits to the register 154 as data to be stored in the register 154 again. That is to say, the register 154 supplies the 9-bit data D152 obtained as a result of the cumulative additions carried out previously to the selector 153 and the adder 156 till data consisting of 9 bits is obtained as a result of cumulatively adding the function values φ(|vi|) obtained for messages D103 (or messages uj) received from all the edges along 1 column of the parity check matrix H.
On the other hand, a FIFO memory 155 delays the message D103 received from a check node to a point of time at which the register 154 supplies new data D152 (Σuj for a summation range starting from i=1 and ending at i=dv) to an adder 156. Then, the FIFO memory 155 supplies the delayed data D103 to the adder 156 as data D153 including 6 bits. The adder 156 subtracts the data D153 supplied by the FIFO memory 155 from the data D152 supplied by the register 154. That is to say, the adder 156 subtracts the message uj received from an edge serving as an object of message computation from the messages D103 (the messages uj) received from all the edges along 1 column of the parity check matrix H, and outputs the difference. The difference is thus the value of Σuj for a summation range starting from j=1 and ending at j=(dv−1). In addition, the adder 156 adds the difference (which is the value of Σuj for a summation range starting from j=1 and ending at j=(dv−1)) to the received data D104 read out from the reception memory 104 in order to produce a sum including 6 bits and outputs the sum as a message D105 (a message vi).
As described above, the variable-node computer 103 carries out a computation process according to Eq. (1) in order to generate a message vi.
It is to be noted that, since the maximum value of the column weight for the parity check matrix H shown in FIG. 9 is 5, that is, since the maximum number of messages supplied to the variable node is 5, the variable-node computer 1031s provided with the FIFO memory 155 for delaying the five messages uj. In a process to handle column messages fewer than the column weight of 5, the magnitude of the delay provided by the FIFO memory 155 can be reduced to a value corresponding to a column weight for the processed column messages.
As described above, the adder 156 subtracts the 6-bit data D153 supplied by the FIFO memory 155 from the 9-bit data D152 supplied by the register 154, producing a difference and, then, the adder 156 adds the difference to the 6-bit received data D104 read out from the reception memory 104 in order to produce a result smaller than a minimum value, which can be represented by a message D105 including 6 bits, or a result greater than a maximum value. If the adder 156 produces a result smaller than the minimum value, which can be represented by a message D105 including 6 bits, the adder 156 clips the result to the minimum value. If the adder 156 produces a result greater than the maximum value, which can be represented by a message D105 including 6 bits, on the other hand, the adder 156 clips the result to the maximum value.
The decoding apparatus shown in FIG. 10 receives control signals from the control section 105 in accordance with weights of the parity check matrix H. Then, by merely changing the control signals, the decoding apparatus is capable of decoding LDPC codes by making use of various parity check matrixes H provided that the storage capacities of the edge memory 100, the edge memory 102, the FIFO memory 127 and the FIFO memory 133, which are employed in the check-node computer 101, and the FIFO memory 155 employed in the variable-node computer 103 are sufficient.
It is to be noted that, at the last decoding stage in the decoding apparatus shown in FIG. 10, a process according to Eq. (5) can be carried out as a substitute for the variable-node process according to Eq. (1) and the result of the process according to Eq. (5) can be output as the final decoding result. This feature is not shown in the figure though.
If the LDPC codes are decoded by making use of a series of decoding apparatus each like the one shown in FIG. 10, the check-node processing and the variable-node processing are carried out alternately. That is to say, in such a series of decoding apparatus each like the one shown in FIG. 10, a variable-node computer 103 carries out the variable-node processing by making use of the result of the check-node processing carried out by a check-node computer 101 whereas a check-node computer 101 carries out the check-node processing by making use of the result of the variable-node processing carried out by a variable-node computer 103.
Thus, in a decoding process making use of a parity check matrix H having 323 edges as shown in FIG. 9, 646 (=323×2) clock pulses are required. In order to carry out 50 decoding processes for example, 108 codes forming received data are handled as a frame. In this case, the number 108 is the code length. While 1 frame is being received, an operation driven by 32,300 (=646×50) clock pulses is necessary. That is to say, an operation of a high speed about 300 (≈32,300/108) times the receiving frequency is necessary. If the receiving frequency is several tens of MHz, an operation of a high speed of at least 1 GHz is necessary.
In a process to decode LDPC codes by making use a series of 50 interconnected decoding apparatus each like the one shown in FIG. 10 for example, while a variable-node computer is carrying out a variable-node process on a first frame, a check-node computer carries out a check-node process on a second frame and another variable-node computer carries out a variable-node process on a third frame and so on. In this way, a plurality of variable-node processes and a plurality of check-node processes can be carried out at the same time. In this case, it is necessary only to carry out computations on 323 edges while 108 codes are being received. Thus, the decoding apparatus only needs to carry out an operation of a high speed equivalent to about 3 (≈323/108) times the receiving frequency, and such an operation can be well implemented. In this case, however, simple estimation indicates that the circuit scale is 50 times the size of the decoding apparatus shown in FIG. 10.
The following description explains a method for implementing a decoding apparatus having a full parallel decoding configuration in which processes of all node are carried out at the same time.
This method for implementing a decoding apparatus having a full parallel decoding configuration is described in documents such as Non-Patent Document 1.
FIG. 13 is a block diagram showing a typical configuration of a decoding apparatus for decoding codes expressed by the parity check matrix H shown in FIG. 9 as codes having a coding rate of ⅔ and a code length of 108.
In the decoding apparatus shown in FIG. 13, all messages received from 323 edges are read out from an edge memory 202 or 206 at the same time and used for generating new messages for the 323 edges. Then, the resulting new messages are stored at the same time respectively in the edge memory 206 or 202 provided at the following stage. Thus, the LDPC codes can be decoded by making use of a series of decoding apparatus each like the one shown in FIG. 13.
The decoding apparatus shown in FIG. 13 includes a reception memory 205, two edge reshuffling devices 200 and 203, the two edge memories 202 and 206 mentioned above, 36 check-node computers 2011 to 20136 and 108 variable-node computers 2041 to 204108. These memories, sections and computers are explained in detail as follows.
The edge memory 206 is used for storing all messages D2061 to D206108 received from respectively variable-node computers 2041 to 204108 provided at the immediately preceding stage at the same time. Then, at the next time (or the next clock timing), the messages D2061 to D206108 are read out as respectively messages D2071 to D207108, which are supplied to an edge reshuffling device 200 provided at the Immediately succeeding stage as messages D200 (strictly speaking, messages D2001 to D200108 respectively). The edge reshuffling device 200 rearranges the order of the messages D2001 to D200108 received from the edge memory 206 in accordance with the parity check matrix H shown in FIG. 9 and supplies the rearranged messages to the check-node computers 2011 to 20136 as messages D2011 to D20136.
The check-node computers 2011 to 20136 carry out the computation process according to Eq. (7) on respectively the messages D2011 to D20136 received from the edge reshuffling device 200 in order to produce messages D2021 to D20236 respectively as a result of the computation process and supplies the messages D2021 to D20236 to the edge memory 202.
The edge memory 202 is used for storing all the messages D2021 to D20236 from the check-node computers 2011 to 20136 respectively at the same time. Then, at the next time, the messages D2021 to D20236 are read out from the edge memory 202 as respectively messages D2031 to D20336, which are supplied to an edge reshuffling device 203 provided at the immediately succeeding stage.
The edge reshuffling device 203 rearranges the order of the messages D2031 to D20336 received from the edge memory 202 in accordance with the parity check matrix H shown in FIG. 9 and supplies the rearranged messages to the variable-node computers 2041 to 204108 as messages D2041 to D204108.
The variable-node computers 2041 to 204108 carry out the computation process according to Eq. (1) on the messages D2041 to D204108 received from the edge reshuffling device 203 and the messages D2051 to D205108 received from the reception memory 205 in order to produce messages D2061 to D206108 respectively as a result of the computation process and supplies the messages D2061 to D206108 to the edge memory 206 provided at the immediately succeeding state.
FIG. 14 is a diagram showing a typical configuration of each of the check-node computers 201m (where m=1, 2, . . . 36) employed in the decoding apparatus shown in FIG. 13 as computers for carrying out check-node processes at the same time.
A check-node computer 201m shown in FIG. 14 carries out a check-node process according to Eq. (7) in the same way as the check-node computer 101 shown in FIG. 11. Check-node processes are, however, carried out at the same time on all edges.
That is to say, in the check-node computer 201m shown in FIG. 14, messages D2211 to D2219 (messages vi) originally received from variable nodes each corresponding to a row of the parity check matrix H shown in FIG. 9 are all acquired at the same time from the edge reshuffling device 200. The 5 less significant bits of each of the messages D2221 to D2229 (vi) are the absolute value (|vi|) of each of the messages D2221 D2229 (vi) respectively, the absolute values (|vi|) being supplied to LUTs 2211 to 2219 respectively. On the other hand, the most significant bit of each of the messages D2211 to D2219 (vi) are the sign of each of the messages D2211 D2219 (vi) respectively. The signs denoted by notations D2231 to D2239 are supplied to EXOR circuits 2261 to 2269 respectively and an EXOR circuit 225.
For the absolute value D2221 to D2221 (|vi|), the LUT 2211 to LUT 2219 reads out 5-bit data D2241 to D2249 (or the 5-bit value of the function (φ(|vi|) used in the computation process according to Eq. (7)) and supplies computation results D2241 to D2249 (φ(|vi|)) to a subtractor 2231 to 2239 and an adder 222.
The adder 222 finds a 9-bit sum D225 of the computation results D2241 to D2249. The sum D225 including 9 bits is the sum of computation results D2241 to D2249 obtained for 1 row of the parity check matrix H. That is to say, the sum D225 consisting of 9 bits is the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=9. The adder 222 supplies the sum D225 including of 9 bits to the subtractors 2231 to 2239. The subtractors 2231 to 2239 subtract the computation results D2241 to D2249 (or the values of the function φ(|vi|)) from the sum D225 to give differences D2271 to D2279 each including 5 bits and supplies to LUT 2241 to 2249. That is to say, the subtractors 2231 to 2239 subtract the value of the function φ(|vi|) obtained for a message vi received from an edge serving as an object of message computation from the sum of the values of the function φ(|vi|) obtained for messages vi received from all edges and outputs the differences D2271 to D2279 each including 5 bits to the LUT 2241 to 2249 respectively. Thus, the differences D2271 to D2279 each including 5 bits are each the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=8. For the differences D2271 to D2279 each including 5 bits respectively, the LUTs 2241 to 2249 read out respectively 5-bit data D2281 to 2289 (or the 5-bit values of the function φ−1 (Σφ(|vi|)) used in the computation process according to Eq. (7)).
On the other hand, an EXOR circuit 225 computes the exclusive logical sum of all the sign bits D2231 to D2239 in order to find a 1-bit product D226 of all the sign bits D2231 to D2239. Then, the EXOR circuit 225 outputs the product D226 including 1 bit to EXOR circuits 2261 to 2269. The product D226 including 1 bit is the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=9. The EXOR circuits 2261 to 2269 find the exclusive logical sum of the product D226 including 1 bit and the sign bits D2231 to D2239 respectively in order to divide the sign bits D2231 to D2239 by the product D226 including 1 bit to give division results D2291 to D2299, which are each the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=8.
A check-node computer 201m outputs messages D2301 to D2309 as a result of the check-node process carried out thereby. The messages D2301 to D2309 are each message including a total of 6 bits. The 5 less significant bits of each of the messages D2301 to D2309 are one of the 5-bit processing results D2281 to D2289 output by the LUT 2241 to 2249 respectively. On the other hand, the most significant bit of each of the messages D2301 to D2309 is one of the division results D2291 to D2299 output by the EXOR circuits 2261 to 2269 respectively.
As described above, a check-node computer 201m carries out a check-node process according to Eq. (7) in order to find a message uj.
It is to be noted that, in the configuration shown in FIG. 14 as the configuration of a check-node computer 201m, each message is quantized into a total of 6 bits including a sign bit. In addition, the circuit shown in FIG. 14 as the circuit of a check-node computer corresponds to 1 check node. There are as many check nodes as rows of the parity check matrix H shown in FIG. 9 as a parity check matrix H serving as the object of the check-node process. Since the parity check matrix H has 36 rows as shown in FIG. 9, the decoding apparatus shown in FIG. 13 includes 36 check-node computers 201m each like the one shown in FIG. 14.
As described above, the check-node computer 201m shown in FIG. 14 is capable of computing nine messages at the same time. In addition, since the row weights of the parity check matrix H shown in FIG. 9 as a parity check matrix serving as the object of the check-node process are 8 for the first row and 9 for each of the second to thirty-sixth rows, that is to say, since the number of messages supplied to the check node is 8 for 1 check-node computer 201m corresponding to the first row having a row weight of 8, or is 9 for 35 check-node computers 201m respectively corresponding to the second to thirty-sixth rows each having a row weight of 9, the check-node computer 201m has a configuration capable of computing 8 messages at the same time in the same way as the circuit shown in FIG. 14 whereas each of the remaining 35 check-node computers 2012 to 20136 has the same configuration as the circuit shown in FIG. 14 and is hence capable of computing 8 messages at the same time in the same way as the circuit shown in FIG. 14.
FIG. 15 is a diagram showing a typical configuration of each of the variable-node computers 204p (where p=1, 2, . . . 108) employed in the decoding apparatus shown in FIG. 13 as computers for carrying out check-node processes at the same time.
A check-node computer 204p shown in FIG. 15 carries out a variable-node process according to Eq. (1) in the same way as the variable-node computer 103 shown in FIG. 12. Variable-node processes are, however, carried out at the same time on all edges.
That is to say, in the variable-node computer 204p shown in FIG. 15, the 6-bit messages D2511 to D2515 (messages uj) received from check nodes each corresponding to a row of the parity check matrix H are all acquired at the same time from the edge reshuffling device 203. The 6-bit messages D2511 to D2515 (or messages uj) are supplied to adders 2521 to 2525 and an adder 251. In addition, the variable-node computer 204p also receives received data D271 from the reception memory 205. The received data D271 is then supplied to the adders 2521 to 2525.
The adder 251 computes a sum D252 including 9 bits as the sum of all the 6-bit messages D2511 to D2515 (or messages uj) and outputs the sum D252 including 9 bits to the adders 2521 to 2525. The sum D252 including 9 bits is the value of Σuj for a summation range starting from j=1 and ending at j=5. The adders 2521 to 2525 subtract the 6-bit messages D2511 to D2515 (or messages uj) respectively from the sum D252. The 6-bit messages D2511 to D2515 (or messages uj) subtracted by the adders 2521 to 2525 respectively from the sum D252 are each a message received from an edge serving as an object of message computation whereas the sum D252 is a result computed from messages uj received from all edges. Thus, the differences obtained as results of subtracting the 6-bit messages D2511 to D2515 (or messages uj) respectively from the sum D252 are each the value of Σuj for a summation range starting from j=1 and ending at j=4.
In addition, the adders 2521 to 2525 add received data D271 (uoi) to the subtracting values (or the values of Σuj for a summation range starting from j=1 and ending at j=4) to give 6-bit sums D2531 to D2535, which are each output as a result of the variable-node process.
As described above, the variable-node computer 204p carries out a variable-node process according to Eq. (1) in order to generate messages vi.
It is to be noted that, in the configuration shown in FIG. 15 as the configuration of a variable-node computer 204p, each message is quantized into a total of 6 bits including a sign bit. In addition, the circuit shown in FIG. 15 corresponds to 1 variable node. There are as many variable nodes as columns of the parity check matrix H shown in FIG. 9 as a parity check matrix H serving as the object of the variable-node process. Since the parity check matrix H has 108 columns as shown in FIG. 9, the decoding apparatus shown in FIG. 13 includes 108 circuits like the one shown in FIG. 15.
Thus, the variable-node computer 204p shown in FIG. 15 is capable of computing five messages at the same time. Since the parity check matrix H shown in FIG. 9 as a parity check matrix serving as the object of the variable-node process has column weights of 5, 3, 2 and 1 on 18, 54, 35 and 1 columns respectively, 18 of the 108 variable-node computers 2041 to 204108 corresponding respectively to 18 columns each having a column weight of 5 each have the same configuration as the circuit shown in FIG. 15. The remaining 54, 35, 1 variable-node computers 204p corresponding respectively to 54, 35, 1 columns each having a column weight of 3, 2, 1 are each capable of computing 3, 2. 1 messages at the same time in the same way as the circuit shown in FIG. 15.
It is to be noted that, at the last decoding stage in the decoding apparatus shown in FIG. 13, a process according to Eq. (5) can be carried out as a substitute for the variable-node process according to Eq. (1) and the result of the process according to Eq. (5) can be output as the final decoding result as is the case with the decoding apparatus shown in FIG. 10. This feature is not shown in the figure though.
As described above, the decoding apparatus shown in FIG. 13 is capable of computing all messages received from 323 edges at the same time in 1 clock.
If LDPC codes are decoded by making use of a series of decoding apparatus each like the one shown in FIG. 13, the check-node processing and the variable-node processing are carried out alternately and it takes time of two clocks to complete one decoding process. Thus, if it is necessary to carry out 50 decoding processes, only 100 (2×50) clock operations need to be performed while receiving received data taking codes with a code length of 108 as 1 frame. As a result, the operating frequency is about equal to the receiving frequency. In general, the LDPC codes have a large code length in a range of several thousands to several tens of thousands. By using the decoding apparatus shown in FIG. 13, it is possible to set a very large number as the number of times the decoding processing is to be carried out. Therefore, improvement of the error correction performance can be expected.
Since the decoding apparatus shown in FIG. 13 computes messages corresponding to all edges of the Tanner graph concurrently, however, the circuit scale of the decoding apparatus increases proportionally to the code length. In addition, if the decoding apparatus shown in FIG. 13 is designed as an apparatus for decoding the LDPC codes defined by a parity check matrix H as codes having a certain code length and a certain coding rate, it will be difficult to decode LDPC codes expressed by a parity check matrix H other than the certain parity check matrix H as codes having a code length other than the certain code length and a coding rate other than the certain coding rate. That is to say, it is difficult to apply the decoding apparatus shown in FIG. 13 to a case in which a variety of codes can be decoded by merely changing control signals as is the case with the decoding apparatus shown in FIG. 10. In other words, the decoding apparatus shown in FIG. 13 exhibits much code dependence.
In addition to the decoding methods adopted by the decoding apparatus shown in FIGS. 10 and 13, there is a decoding method described in documents such as Non-Patent Document 2 as a decoding method for decoding neither one message at one time nor all messages at the same time, that is, as a decoding method for decoding four messages at one time. The decoding method described in Non-Patent Document 2 has a problem that, in general, it is not easy to avoid operations to read out data from different addresses in a memory at the same time and operations to write data into different addresses in the memory at the same time. That is to say, it is hard to control accesses to the memory.
In order to solve the problem described above, there has been reported a coding and decoding apparatus (for example, referred to as Non-Patent Documents 3 and 4) as an apparatus much suitable for implementation of a decoder for decoding partially parallel codes instead of decoding random codes. However, a method for implementing the decoding apparatus described in Non-Patent Document 3 is a method devised for specific codes. With this method, it is thus difficult to decode codes having a variety of code lengths and a variety of coding rates.
Documents such as Patent Document 1 describe a decoding apparatus capable of decoding codes having a variety of code lengths and a variety of coding rates if the codes are LDPC codes expressed by a parity check matrix H like one shown in FIG. 16. As shown in the figure, the parity check matrix H is a matrix that can be represented as a combination of 6×6 unit matrixes, a matrix obtained by setting one or more of the “1” elements of a unit matrix to 0 (hereinafter referred to as semi unit matrixes accordingly), a matrix obtained by carrying out a cyclic shift operation on a unit matrix or a semi unit matrix (hereinafter referred to as shift matrixes accordingly), a matrix obtained by computing the sum of at least any two of a unit matrix, a semi unit matrix and a shift matrix (or the sum of a plurality such matrixes)(hereinafter referred to as sum matrixes accordingly) and 0 matrixes including a 6×6 matrix each having all elements thereof set to 0. The decoding apparatus is also capable of decoding codes having a variety of code lengths and a variety of coding rates if the codes are LDPC codes according to the transposed matrix of the parity check matrix H shown in FIG. 16 as a matrix that can be expressed as a combination of the these matrixes.
It is to be noted that the parity check matrix H shown in FIG. 16 is obtained by providing a gap between any two adjacent 6×6 matrixes included in the parity check matrix H shown in FIG. 9. In the following description, the unit matrix, the semi unit matrix, the shift matrix, the sum matrix and the 0 matrix, which are combined to form the parity check matrix H shown in FIG. 16, are each properly referred to as a component matrix.
By referring to FIGS. 17 to 22, the following description explains a decoding apparatus for decoding LDPC codes that can be expressed by the parity check matrix H shown in FIG. 16.
FIG. 17 is a block diagram showing a typical configuration of a decoding apparatus 400 for decoding LDPC codes that can be expressed by the parity check matrix H shown in FIG. 16.
The decoding apparatus 400 employs a decoding intermediate result storage memory 410, a cyclic shift circuit 411, a computation section 412 having six computers 4121 to 4126, a decoding intermediate result storage memory 413, a cyclic shift circuit 414, a computation section 415 having six computers 4151 to 4156, a reception memory 416 and a control section 417.
Computation processes carried out by the computers 412k and the computers 415k (where k=1, 2, . . . and 6) are explained by making use of equations as follows.
To put it concretely, the computation section 412 carries out a first computation process according to Eq. (7) given earlier and Eq. (8) shown below in order to generate a decoding intermediate result uj as the result of the first computation process and supplies to the decoding intermediate result storage memory 410. Computation section 415 carries out a second computation process according to Eq. (5) given earlier in order to generate a decoding intermediate result v as the result of the second computation process and supplies to the decoding intermediate result storage memory 410.
[Eq. 8]vi=v−udv  (8)
It is to be noted that notation udv used in Eq. (8) denotes an intermediate result received from an edge, which is included in the ith column of the parity check matrix H as an edge serving as an object of message computation, as a result of a check-node process. In this case, the intermediate result is the check-node process result itself. That is to say, notation udv denotes a decoding intermediate result for an edge serving as an object of message computation.
That is to say, the decoding intermediate result v obtained as a result of the second computation process according to Eq. (5) given before is the sum of the received value uoi and decoding intermediate results uj generated from all edges corresponding to matrix elements each set at 1 at intersections of rows and the ith column in the parity check matrix H as decoding intermediate results of check-node processes. Thus, the value vi used in Eq. (7) is a difference obtained as a result of subtracting the decoding intermediate result udv received from an edge serving as an object of message computation as the decoding intermediate result of a check-node process from the decoding intermediate result v obtained as a result of the second computation process according to Eq. (5). The decoding intermediate result udv is one of the decoding intermediate results uj generated from all edges corresponding to matrix elements each set at 1 at intersections of rows and the ith column in the parity check matrix H as decoding Intermediate results of check-node processes. That is to say, the computation process expressed by Eq. (1) as a process to compute the value vi used in the computation process according to Eq. (7) is a computation process carried out as a combination of the computation process according to Eq. (5) and Eq. (8).
Thus, in the decoding apparatus 400, the computation section 412 carries out the first computation process according to Eqs. (7) and (8) alternately with the second computation process carried out by the computation section 415 in accordance with Eq. (5). Then, the computation section 415 outputs the result of the last second computation process as a decoding result. In this way, the decoding apparatus 400 is capable of carrying out a decoding process repeatedly to decode LDPC codes.
It is to be noted that the decoding intermediate result uj obtained as a result of the first computation process according to Eqs. (7) and (8) is equal to the result uj of the check-node process according to Eq. (7).
In addition, since the value v obtained as a result of the second computation process according to Eq. (5) is a result of adding the result uj received from an edge serving as an object of message computation as the result of a check-node process to the result vi of the variable-node process according to Eq. (1), only one value v is found for 1 column of the parity check matrix H (or for one variable node).
In the decoding apparatus 400, the computation section 412 makes use of the decoding intermediate result v produced in the second computation process carried out by the computation section 415 as a result corresponding to columns of the parity check matrix H in execution of the first computation process. The computation section 412 generates a decoding intermediate result uj as the result of the first computation process and supplies to the decoding intermediate result storage memory 413. The decoding intermediate result uj is generated from an edge corresponding to a matrix element set at 1 at an intersection of a row and the ith column in the parity check matrix H as a decoding intermediate result of a check-node process of a check node outputting a message through the edge. Thus, the storage capacity of the decoding intermediate result storage memory 413 is equal to the product obtained as a result of an operation to multiply the number of one matrix elements in the parity check matrix H (that is, the number of all edges) by the number of quantization bits as is the case with the storage capacity of a memory used for storing results of check-node processes.
On the other hand, the computation section 415 makes use of the decoding intermediate results uj generated from all edges corresponding to matrix elements each set at “1” at intersections of rows and the ith column in the parity check matrix H as decoding intermediate results of second computation processes carried out by the computation section 412 and makes use of received data uoi in order to carry out the second computation process and stores a decoding intermediate result v corresponding to the ith column in the decoding intermediate result storage memory 410 as a result of the second computation process. Thus, the storage capacity of the decoding intermediate result storage memory 410 is equal to the product obtained as a result of an operation to multiply the number of columns smaller than the number of matrix elements each set at 1 in the parity check matrix H, that is, the code length of the LDPC codes by the number of quantization bits of the decoding intermediate result v.
As a result, the storage capacity of the decoding intermediate result storage memory 410 can be reduced to a value smaller than the storage capacity of a memory used for storing the result of a variable-node process. Thus, the circuit scale of the decoding apparatus 400 can be decreased.
Next, operations carried out by the sections employed in the decoding apparatus 400 shown in FIG. 17 are explained in detail as follows.
The decoding intermediate result storage memory 410 is used for storing six decoding intermediate results D415 generated by the computation section 415 as a result of the second computation process carried out by the computation section 415. The six decoding intermediate results D415 generated by the computation section 415 are sequentially stored (memory) in the decoding intermediate result storage memory 410 at storage locations starting with a first address.
To put it in detail, at the first address in the decoding intermediate result storage memory 410, the first to sixth decoding intermediate results v are stored as a part of decoding intermediate results corresponding to the columns of the parity check matrix H. Then, by the same token, at a second address, the seventh to twelfth decoding intermediate results v are stored. Subsequently, in the same way, at a third address, the thirteenth to eighteenth decoding intermediate results v are stored. Thereafter, the same operation to store six decoding intermediate results v at an address of a sequence of addresses starting with a fourth address is carried out repeatedly in a similar manner till the 103rd to 108th decoding intermediate results v are stored in an eighteenth address. As a result, 108 decoding intermediate results v are stored in the decoding intermediate result storage memory 410. Thus, the number of words in the decoding intermediate result storage memory 410 is a quotient of 18 obtained as a result of dividing the integer 108 which is the number of columns (the code length of LDPC codes) composing the parity check matrix H shown in FIG. 16 by the integer 6 which is the number of decoding intermediate results at the same time in one operation described above.
In addition, the decoding intermediate result storage memory 410 selects six decoding intermediate results v corresponding to matrix elements each set at “1” on a row included in the parity check matrix H as a row corresponding to a decoding intermediate result uj to be found by the computation section 412 at a succeeding stage from the decoding intermediate results D415 already stored in the decoding intermediate result storage memory 410 and outputs the six selected decoding intermediate results v to the cyclic shift circuit 411 at the same time as a decoding intermediate result D410.
It is to be noted that the decoding intermediate result storage memory 410 typically employs single-port RAMs allowing operations to store and read out six decoding intermediate results in any of the RAMs at the same time. In addition, the decoding intermediate result storage memory 410 is also used for storing a decoding intermediate result D414 produced by the second computation process carried out by the computation section 415 as a result corresponding to a column. Thus, the required storage capacity of the decoding intermediate result storage memory 410, that is, the maximum amount of data that can be stored in the decoding intermediate result storage memory 410, is equal to a product obtained as a result of an operation to multiply the quantization-bit count of the decoding intermediate result D414 by the number of columns (the code length of LDPC codes) in the parity check matrix H.
The cyclic shift circuit 411 receives six decoding intermediate results D410 from the decoding intermediate result storage memory 410 and a control signal D619 from the control section 417. The control signal D619 is information on the number of cyclic shift operations to be carried out on components matrixes such as unit matrixes composing the parity check matrix H. To put it concretely, the information is matrix data representing the number of matrix elements each set at 1 in the parity check matrix H as a matrix element corresponding to one of the decoding intermediate results D410. On the basis of the control signal D619, the cyclic shift circuit 411 carries out cyclic shift operations to rearrange the six decoding intermediate results D410 and outputs the result of the arrangement to the computation section 412 as decoding intermediate results D411.
As described above, the computation section 412 employs the six computers 4121 to 4126. The computation section 412 receives the six decoding intermediate results D411 (v) from the cyclic shift circuit 411 as a result of the second computation process carried out by the computation section 415. In addition, the computation section 412 also receives six decoding intermediate results D413 (uj) from the decoding intermediate result storage memory 413 as a result of the first computation process previously carried out by the six computers 4121 to 4126. The six decoding intermediate results D411 and the six decoding intermediate results D413 are supplied to the six computers 4121 to 4126 respectively. On top of that, the computation section 412 also receives the control signal D419 from the control section 417. In the computation section 412, the control signal D419 is supplied to all the six computers 4121 to 4126. It is to be noted that the control signal D419 is a signal common to the six computers 4121 to 4126.
The six computers 4121 to 4126 each carry out the first computation process according to Eqs. (7) and (8) by making use of one of the six decoding intermediate results D411 (v) and one of the six decoding intermediate results D413 in order to find six decoding intermediate results D412 (vi) corresponding to six matrix elements each set at 1 in the parity check matrix H. Then, the computation section 412 outputs the six decoding intermediate results D412 obtained as a result of the processes carried out by the six computers 4121 to 4126 respectively to the decoding intermediate result storage memory 413.
The decoding intermediate result storage memory 413 typically employs two single-port RAMs allowing operations to write and read out six decoding intermediate results to and from any of the RAMs at the same time. The decoding intermediate result storage memory 413 receives the six decoding intermediate results D412 from the computation section 412 and a control signal D420 from the control section 417 as a signal for controlling an operation to write and read out the six decoding intermediate results D413 to and from the decoding intermediate result storage memory 413.
The decoding intermediate result storage memory 413 allows the six decoding intermediate results D412 received from the computation section 412 to be collectively stored therein and six decoding intermediate results D412 already stored in the decoding intermediate result storage memory 413 to be read out at the same time on the basis of the control signal D420. The decoding intermediate result storage memory 413 supplies the six decoding intermediate results D412 already stored therein to the computation section 412 and the cyclic shift circuit 414 as the six decoding intermediate results D413. That is to say, the decoding intermediate result storage memory 413 allows an operation to read out six decoding intermediate results D413 to be supplied to the computation section 412 and the cyclic shift circuit 414 and an operation to store the six decoding intermediate results D412 received from the computation section 412 at the same time.
It is to be noted that the decoding intermediate results D412 resulting from the first computation process carried out by the computation section 412 are stored in the decoding intermediate result storage memory 413 as messages each generated from an edge corresponding to a matrix element set at 1 at an intersection of a row and the ith column in the parity check matrix H. Thus, the required storage capacity of the decoding intermediate result storage memory 413, that is, the amount of data that can be stored in the decoding intermediate result storage memory 413, is equal to a product obtained as a result of an operation to multiply the quantization-bit count of the decoding intermediate result D412 by the number of matrix elements each set at 1 in the parity check matrix H.
The cyclic shift circuit 414 receives six decoding intermediate results D413 (decoding intermediate results uj) from the decoding intermediate result storage memory 413 and a control signal D421 from the control section 417. The control signal D421 is information on the number of cyclic shift operations to be carried out on components matrixes such as unit matrixes composing the parity check matrix H. To put it concretely, the information is matrix data representing the number of matrix elements each set at 1 in the parity check matrix H as a matrix element corresponding to one of the decoding intermediate results D413. On the basis of the control signal D421, the cyclic shift circuit 414 carries out cyclic shift operations to rearrange the six decoding intermediate results D413 and outputs the result of the arrangement to the computation section 415 as decoding intermediate results D414.
As described earlier, the computation section 415 employs the six computers 4151 to 4156. The computation section 415 receives the six decoding intermediate results D414 from the cyclic shift circuit 414. The six decoding intermediate results D414 are supplied to the 6 computers 4151 to 4156 respectively. In addition, the computation section 415 also receives six pieces of received data D417 (or the LDPC codes) from the reception memory 417. The received data D417 are supplied to the six computers 4151 to 4156 respectively. On top of that, the computation section 417 also receives a control signal D422 from the control section 417. The control signal D422 is supplied to the computers 4151 to 4156. It is to be noted that the control signal D422 is a signal common to the computers 4171 to 4176.
The computers 4151 to 4156 each carry out the second computation process according to Eq. (5) by making use of the decoding intermediate results D414 and the decoding intermediate results D417 in order to find decoding intermediate results D415. Then, the computation section 415 supplies the six decoding intermediate results D415 (v) obtained as a result of the second computation processes carried out by the computers 4151 to 4156 respectively to the decoding intermediate result storage memory 410. If the process presently carried out by the computation section 415 is the last second computation process, the six decoding intermediate results D415 obtained as a result of the processes are output as the final decoding result.
The reception memory 416 is a memory used for storing received data D416, which is data (received data) of a received LLR (Log Likelihood Ratio) serving as the value of a 0 likelihood computed from an incoming value (or a sign bit) D416 received from a transmission line as the 0 likelihood of the sign bit.
To put it in detail, at a first address in the reception memory 416, received data D416 corresponding to the first to sixth columns of the parity check matrix H are stored as a part of received data D416 corresponding to the columns of the parity check matrix H. Then, by the same token, at a second address, received data D416 corresponding to the seventh to twelfth columns of the parity check matrix H are stored. Subsequently, in the same way, at a third address, received data D416 corresponding to the thirteenth to eighteenth columns of the parity check matrix H are stored. Thereafter, the same operation to store six pieces of received data D416 at an address in a sequence of addresses starting with a fourth address is carried out repeatedly in a similar manner till received data D416 corresponding to the 19th to 108th columns of the parity check matrix H are stored in an eighteenth address.
Then, pieces of received data D416 already stored in the reception memory 616 are read out in 6-piece units sequentially one unit after another in an order required by a variable-node process and supplied to the computation section 415 as received data D417.
It is to be noted that the reception memory 416 typically employs single-port RAMs allowing operations to write and read out six pieces of received data to and from any of the RAMs at the same time. Thus, the required storage capacity of the reception memory 416, that is, the maximum amount of data that can be stored in the reception memory 416, is equal to a product obtained as a result of an operation to multiply the quantization-bit count of the received data D416 by the code length of the LDPC codes. In addition, the number of words in the reception memory 416 is a quotient of 18 obtained as a result of dividing the integer 108 by the integer 6. In this case, the integer 108 is the number of columns composing the parity check matrix H, that is the code length of the LDPC codes whereas the integer 6 is the number of pieces of received data D417 read out at the same time in one operation described above.
The control section 417 supplies the control signal D418 to the cyclic shift circuit 411 in order to control the cyclic shift circuit 411 and the control signal D419 to the computation section 412 in order to control the computation section 412. In addition, the control section supplies the control signal D420 to the decoding intermediate result storage memory 413 in order to control the decoding intermediate result storage memory 413, the control signal D421 to the cyclic shift circuit in order to control the cyclic shift circuit 414 and the control signal D421 to the computation section 415 in order to control the computation section 415.
Data is circulated for one decoding process in the decoding apparatus 400 in the following order: the decoding intermediate result storage memory 410 to the cyclic shift circuit 411 to the computation section 412 to the decoding intermediate result storage memory 413 to the cyclic shift circuit 414 and to the computation section 415. After the decoding apparatus 400 carries out the decoding process repeatedly a predetermined number of times, the decoding intermediate results D415 obtained as a result of the second computation processes carried out by the computation section 415 are output as the final decoding result.
FIG. 18 is a block diagram showing a typical configuration of a computation section 4121 employed in the computation section 412 shown in FIG. 17.
It is to be noted that, even though the computation section 4121 is explained by referring to FIG. 18, the explanation also applies to the computers 4122 to 4126.
In the configuration shown in FIG. 18 as the configuration of the computation section 412, each decoding intermediate result (udv) obtained as a result of the first computation process carried out previously by the computation section 412 is quantized into data including 6 bits including a sign bit whereas each decoding intermediate result (v) obtained as a result of the second computation process carried out by the computation section 415 is quantized into data including 9 bits. In addition, the computer 4121 shown in FIG. 18 receives a clock signal ck to be provided to necessary blocks. Thus, each block employed in the computer 4121 carries out an operation synchronously with the clock signal ck.
On the basis of the control signal D419 received from the control section 417, the computer 4121 shown in FIG. 18 carries out the first computation process according to Eqs. (7) and (8) by making use of a decoding intermediate result D413 (udv) obtained as a result of the first computation process performed earlier by the computation section 412 and one of decoding intermediate results D411 (v) supplied sequentially one result after another by the cyclic shift circuit 411. The decoding intermediate results D413 (udv) are read out from the decoding intermediate result storage memory 413 sequentially one result after another.
To be more specific, the computer 4121 receives one of six 9-bit decoding intermediate result D411 (v) supplied sequentially one result after another by the cyclic shift circuit 411 and a decoding intermediate result D413 (udv) selected from six 6-bit decoding intermediate results D413 (uj) read out from the decoding intermediate result storage memory 413 sequentially one result after another. As described above, the 6-bit decoding intermediate result D413 (udv) is obtained as a result of the first computation process performed earlier by the computation section 412. In the computer 4121, the decoding intermediate result D411 (v) including 9 bits and the decoding intermediate result D413 (udv) including bits are supplied to an adder 431. In addition, the computer 4121 also receives the control signal D419 from the control section 417. The control signal D419 is supplied to selectors 435 and 442.
The adder 431 subtracts the decoding intermediate result D413 (uj) including 6 bits from the decoding intermediate result D411 (v) including 9 bits to yield a difference D431 including 6 bits. That is to say, the adder 431 carries out an operation according to Eq. (8) in order to produce the difference D431 (vi) as the result of the operation.
The 1-bit sign bit D432 (sign (vi)) of the 6-bit difference D431 generated by the adder 431 is supplied to an EXOR circuit 440 whereas the 5 less significant bits D433 (|vi|) of the difference D431 including 6 bits are supplied to a LUT 432. The sign bit D432 (sign (vi)) representing the plus/minus sign of the 6-bit difference D431 is the most significant bit of the 6-bit difference D431.
For the absolute value D433 (|vi|) supplied to the LUT 432, the LUT 432 reads out 5-bit data D434 (φ(|vi|) used in the computation process according to Eq. (7)) from a table and supplies the data D434 (φ(|v1|)) to an adder 433 and a FIFO memory 438.
The adder 433 cumulatively adds the data D434 (or the value of the function φ(|vi|)) to 9-bit data D435 stored in a register 434 in order to compute a sum D434 including 9 bits and stores the sum D434 back in the register 434. It is to be noted that this cumulative addition process is carried out repeatedly and, as the cumulative addition process is completed to find the final cumulative addition result for the absolute values D433 (|vi|) found from the decoding intermediate results D411 corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H, the contents of the register 434 are reset.
After receiving decoding intermediate results D411 corresponding to a row of the parity check matrix H sequentially one result after another and sequentially adding the results D411 to the data D434 stored in the register 434 in a cumulative manner, the control section 417 changes the control signal D419 supplied thereby from 0 to 1. In the case of a row weight of 9 for example, the control signal D419 stays at 0 during a period covering the first to eighth clock pulses. As the ninth clock pulse is generated, the control section 417 changes the control signal D419 to 1.
With the control signal D419 set at 1, a selector 435 selects the data stored in the register 434 and supplies the data to a register 436 to be stored in the register 436 as data D436. The data stored in the register 434 with the control signal D419 set at 1 is 9-bit data D435 obtained as a result of cumulatively adding the function values φ(|vi|) found from decoding intermediate results D411 (or decoding intermediate results v) corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H. That is to say, the cumulative 9-bit data D435 is the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=dc. The data D436 stored in the register 436 is supplied to the selector 435 and an adder 437 as data D437 including 9 bits. With the control signal D419 reset at 0, on the other hand, the selector 435 selects the 9-bit data D437 received from the register 436 and outputs the selected data D437 to the register 436 as data to be stored in the register 436 again. That is to say, the register 436 supplies the 9-bit data D437 obtained as a result Σφ(|vi|) of the cumulative additions carried out previously to the selector 435 and the adder 437 till data including 9 bits is obtained as a result Σφ(|vi|) of cumulatively adding the function values φ(|vi|) found from the decoding intermediate results D411 (or the decoding intermediate results v) corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H.
On the other hand, a FIFO memory 438 delays the computation result D434 (φ(|vi|)) received from the LUT 432 to a point of time at which the register 436 supplies new data D437 (Σφ(|vi|) for a summation range starting from i=1 and ending at i=dc) to the adder 437. Then, the FIFO memory 438 supplies the delayed data D434 to an adder 437 as data D438 including 5 bits. The adder 437 subtracts the data D438 supplied by the FIFO memory 438 from the data D437 supplied by the register 436. That is to say, the adder 437 subtracts a decoding intermediate result corresponding to an edge serving as an object of message computation, that is, the function value φ(|vi|) found from the decoding intermediate result D411 (or the decoding intermediate result v) corresponding to a predetermined matrix element set at 1 on 1 row of the parity check matrix H, from the result Σφ(|vi|) of cumulatively adding the function values φ(|vi|) found from the decoding intermediate results D411 (or the decoding intermediate results v) corresponding to all matrix elements set at 1 on the row of the parity check matrix H, and outputs the difference to a LUT 439 as a difference D439. The difference D439 is thus the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=(dc−1).
For the difference D439 representing the value of Σφ(|vi|) for a summation range starting from i=1 and ending at i=(dc−1), the LUT 439 reads out a 5-bit computation result D440 (φ−1(Σφ(|vi|)) used in the computation process according to Eq. (7)).
Concurrently with the processing described above, an EXOR circuit 440 computes the exclusive logical sum of 1-bit data D442 stored in a register 441 and the sign bit D432. That is to say, the EXOR circuit 440 computes the product of two sign bits. The multiplication result D441 including 1 bit is stored back in the register 441. It is to be noted that, when the sign bits D432 extracted from the decoding intermediate results D411 corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H have been subjected to the multiplication process carried out by the EXOR circuit 440, the contents of the register 441 are reset.
When the multiplication result D441 (or the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=dc) obtained from the multiplication processes carried out on the sign bits D432 extracted from the decoding intermediate results D411 corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H is stored in the register 441, the control section 417 changes the control signal D419 supplied thereby from 0 to 1.
With the control signal D419 set at 1, a selector 442 selects the multiplication result D442 (Π sign (vi) for a multiplication range starting from i=1 and ending at i=dc) stored in the register 441 and supplies the multiplication result D442 to a register 443 as 1-bit data D443 to be stored in the register 443. As described above, the multiplication result D442 is a 1-bit data obtained as a result of the multiplication processes carried out by the EXOR circuit 445 on the sign bits D432 extracted from the decoding intermediate results D411 corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H. The data D443 stored in the register 443 is supplied to the selector 442 and an EXOR circuit 445 as data D444 including 1 bit. With the control signal D419 reset at 0, on the other hand, the selector 442 selects the data D444 received from the register 443 and outputs to the register 443 as data to be stored in the register 443 again. That is to say, the register 443 supplies the data already stored therein to the selector 442 and the EXOR circuit 445 till data is obtained as a result of the multiplication processes on the sign bits D432 extracted from the decoding intermediate results D411 (or the decoding intermediate results v) corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H.
On the other hand, the FIFO memory 444 delays the sign bit D432 to a point of time at which the register 443 supplies new data D444 (or the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=dc) to the EXOR circuit 445. Then, the FIFO memory 444 supplies the delayed sign bit D432 to the EXOR circuit 445 as data D445 including 1 bit. The EXOR circuit 445 computes an exclusive logical sum of the data D444 received from the register 443 and the 1-bit data D445 received from the FIFO memory 444 in order to divide the data D444 by the data D445, and outputs the division result consisting of 1 bit as data D446. That is to say, the EXOR circuit 445 divides a product of decoding intermediate results D432 (sign (vi)) extracted from decoding intermediate results D411 corresponding to all matrix elements set at 1 on 1 row of the parity check matrix H by the sign bit D432 (sign (vi)) extracted from a decoding intermediate result D411 corresponding to a predetermined matrix element set at 1 on the row of the parity check matrix H, and outputs the division result (or the value of Π sign (vi) for a multiplication range starting from i=1 and ending at i=(dc−1)) as the division result D446.
The computer 4121 concatenates the 5-bit processing result D440 generated by the LUT 439 with the 1-bit division result D446 produced by the EXOR circuit 445 by taking the processing result D440 including 5 bits as 5 less significant bits and the division result D446 including 1 bit as the most significant bit in order to output a decoding intermediate result D412 (or a decoding intermediate result uj) including a total of 6 bits.
As described above, the computer 1421 carries out the computation processing according to Eqs. (7) and (8) in order to find a decoding intermediate result uj.
It is to be noted that, since the maximum value of the row weight for the parity check matrix H shown in FIG. 16 is 9, that is, since the maximum number of decoding intermediate results D411 (v) and decoding intermediate results D413 (udv) supplied to the computer 4121 are each 9, the computer 4121 is provided with the FIFO memory 438 for delaying the nine decoding intermediate results D434 (or the values of the function φ(|vi|)) and the FIFO memory 444 for delaying the nine sign bits D432. In a process to handle row messages fewer than the row weight of 9, the magnitude of the delay provided by the FIFO memory 438 and the FIFO memory 444 can be reduced to a value corresponding to the row weight.
FIG. 19 is a block diagram showing a typical configuration of a computer 4151 employed in the computation section 415 shown in FIG. 17.
It is to be noted that, even though only the computer 4151 is explained by referring to FIG. 19, the explanation also applies to the computers 4152 to 4156.
In the configuration shown in FIG. 19 as the configuration of the computer 4151, each decoding intermediate result (uj) obtained as a result of the first computation process carried out by the computation section 412 is quantized into a total of 6 bits including a sign bit. In addition, the computer 4151 shown in FIG. 19 receives a clock signal ck providing the necessary clock signal ck to the computer 4151. Thus, each block employed in the computer 4151 carries out an operation synchronously with the clock signal ck.
On the basis of a control signal D422 received from the control section 417, the computer 4151 shown in FIG. 19 carries out the second computation process according to Eq. (5) by making use of pieces of received data D417 (or received values uoi) sequentially read out from the reception memory 416 one piece after another and decoding intermediate results D414 (uj) sequentially read out from the cyclic shift circuit 414 one result after another.
That is to say, the computer 4151 reads out 6-bit decoding intermediate results D414 (or decoding intermediate results uj) corresponding to matrix elements set at 1 on rows of the parity check matrix H from the cyclic shift circuit 414 sequentially one result after another from the cyclic shift circuit 414, supplying the decoding intermediate results D414 to an adder 471. In addition, the computer 4151 reads out pieces of 6-bit received D417 from the reception memory 416 sequentially one piece after another, supplying the pieces of 6-bit received D417 to an adder 475. On top of that, the computer 4151 receives a control signal D422 from the control section 417 and supplies the control signal D422 to a selector 473.
The adder 471 adds the decoding intermediate result D414 (or the decoding intermediate result uj) to 9-bit data D471 stored in a register 472 in order to produce a cumulative decoding intermediate D414 consisting of 9 bits and stores the cumulative decoding intermediate result D414 consisting of 9 bits also in the register 472. It is to be noted that, after the decoding intermediate results D414 corresponding to all matrix elements set at 1 on 1 column of the parity check matrix H are cumulatively added and stored in the register 472, the contents of the register 472 are reset.
After the computer 4151 reads out decoding intermediate results D414 corresponding to all matrix elements set at 1 on 1 column of the parity check matrix H sequentially one result after another and stores the cumulative decoding intermediate result D414 to the register 472, the control section 417 changes the control signal D422 supplied thereby from “0” to “1”. In the case of a column weight of “5” for example, the control signal D422 stays at “0” during a period covering the first to fourth clock pulses. As the fifth clock pulse is generated, the control section 417 changes the control signal D422 from “0” to “1”.
With the control signal D422 set at “1”, a selector 473 selects the value stored in the register 472, that is the 9-bit cumulative sum D471 (value of Σuj for a summation range starting from j=1 and ending at j=dv) stored in the register 472 and supplies the cumulative sum D471 consisting of 9 bits to a register 474 to be stored in the register 474. The cumulative sum D471 stored in the register 472 is a 9-bit value obtained as a result of cumulatively adding the decoding intermediate results D414 (or decoding intermediate results uj) received from all the edges along 1 column of the parity check matrix H. The data D471 stored in the register 474 is supplied to the selector 471 and an adder 475 as data D472 consisting of 9 bits. With the control signal D422 reset at “0”, on the other hand, the selector 473 selects the data D472 received from the register 474 and outputs to the register 474 as data to be stored in the register 474 again. That is to say, the register 474 supplies the 9-bit data D472 obtained as a result of the cumulative additions carried out previously to the selector 473 and the adder 475 till the decoding intermediate results D414 (or decoding intermediate results uj) received from all the edges along 1 column of the parity check matrix H are added to each other in order to give a cumulative sum.
The adder 475 adds the data D472 consisting of 9 bits to the 6-bit data D417 received from the reception memory 416 and outputs a decoding intermediate result D415 (or a decoding intermediate result v) obtained as the result of the addition operation.
As described above, the computer 4151 carries out a process according to Eq. (5) in order to produce the decoding intermediate result v.
It is to be noted that, since the maximum value of the column weight for the parity check matrix H shown in FIG. 9 is 5, that is, since the maximum number of decoding intermediate results uj supplied to the computer 4151 is 5, the computer 4151 adds up to five decoding intermediate results uj each consisting of 6 bits in order to give a cumulative sum. Thus, the output of the computer 4151 consists of 9 bits.
FIG. 20 is a block diagram showing a typical configuration of the decoding intermediate result storage memory 413 shown in FIG. 17.
The decoding intermediate result storage memory 413 employs switches 501 and 504 as well as two decoding intermediate result storage RAMs 502 and 503, which are each a single-port RAM.
Before every component employed in the decoding intermediate result storage memory 413 is described in detail, first of all, a method for storing data in the decoding intermediate result storage RAMs 502 and 503 is described.
The decoding intermediate result storage RAMs 502 and 503 are each used for storing decoding intermediate results D412 supplied to the decoding intermediate result storage RAMs 502 and 503 by way of the switch 501 as a result of the first computation process carried out by the computation section 412.
To put it concretely, at first to ninth addresses in the decoding intermediate result storage RAM 502, decoding intermediate results D412 (D501) corresponding to matrix elements set at 1 on the first to sixth rows of the parity check matrix H shown in FIG. 16 are stored in a form of packing (by ignoring matrix elements reset to 0) decoding intermediate results D412 corresponding to matrix elements set at 1 on the rows in the horizontal direction (or the column arrangement direction).
Let notation (j, i) denote an intersection of the jth row and the ith column in the parity check matrix H shown in FIG. 16. In this case, decoding intermediate results D412 corresponding to matrix elements set at 1 in a 6×6 unit matrix included in the parity check matrix H shown in FIG. 16 as a component matrix spread throughout a matrix area ranging over intersections (1, 1) to (6, 6) are stored at the first address in the decoding intermediate result storage RAM 502. By the same token, decoding intermediate results D412 corresponding to matrix elements set at 1 in a 6×6 shift matrix included in the parity check matrix H shown in FIG. 16 as a component matrix spread throughout a matrix area ranging over intersections (1, 25) to (6, 30) are stored at the second address. The shift matrix in this case is a shift matrix obtained by carrying out a cyclic shift operation on a 6×6 unit matrix by 5 matrix elements in the direction to the right. In the same way, decoding intermediate results D412 corresponding to matrix elements set at 1 in 6 component matrixes included in the parity check matrix H shown in FIG. 16 are stored at the third to eighth addresses. Likewise, decoding intermediate results D412 corresponding to matrix elements set at 1 in a 6×6 shift matrix included in the parity check matrix H shown in FIG. 16 as a component matrix spread throughout a matrix area ranging over intersections (1, 102) to (6, 108) are stored at the ninth address. The shift matrix in this case is a shift matrix obtained by carrying out a cyclic shift operation on a 6×6 semi unit matrix by 1 matrix element in the direction to the right. The 6×6 semi unit matrix in this case is a semi unit matrix obtained by resetting the matrix element set at 1 on the first row of a 6×6 unit matrix to 0. In this case, the first row of the 6×6 shift matrix spread throughout a matrix area ranging over intersections (1, 102) to (6, 108) does not include a matrix element set at 1. Thus, no decoding intermediate results D412 are stored at the ninth address.
By the same token, at tenth to eighteenth addresses in the decoding intermediate result storage RAM 502, decoding intermediate results D412 (D501) corresponding to matrix elements set at 1 on the thirteenth to eighteenth rows of the parity check matrix H shown in FIG. 16 are stored. To put it in detail, decoding intermediate results D412 corresponding to matrix elements set at 1 in a 6×6 shift matrix included in the parity check matrix H shown in FIG. 16 as a component matrix spread throughout a matrix area ranging over intersections (13, 7) to (18, 12) are stored at the tenth address. The shift matrix in this case is a shift matrix obtained by carrying out a cyclic shift operation on a 6×6 unit matrix by 5 matrix elements in the direction to the right. By the same token, decoding intermediate results D412 corresponding to matrix elements set at 1 in a shift matrix serving as a component of a sum matrix included in the parity check matrix H shown in FIG. 16 as a component matrix spread throughout a matrix area ranging over intersections (13, 13) to (18, 18) are stored at the eleventh address. The sum matrix in this case is the sum of a 6×6 unit matrix and the shift matrix, which is obtained by carrying out a cyclic shift operation on a 6×6 unit matrix by 1 matrix element in the direction to the right. Likewise, decoding intermediate results D412 corresponding to matrix elements set at 1 in the 6×6 the unit matrix serving as a component of the sum matrix included in the parity check matrix H shown in FIG. 16 as a component matrix spread throughout a matrix area ranging over intersections (13, 13) to (18, 18) are stored at the twelfth address. Thereafter, in the same way, decoding intermediate results D412 corresponding to matrix elements set at 1 in component matrixes included in the parity check matrix H shown in FIG. 16 are stored at the thirteenth to eighteenth addresses.
That is to say, in the case of a component matrix having a weight 2 or more, the component matrix is expressed in the form of a sum matrix obtained by computing the sum of a P×P unit matrix having a weight of 1, a semi unit matrix having a weight of 1 and a shift matrix having a weight of 1. As described earlier, a semi unit matrix is a matrix obtained by setting one or more of the elements set at 1 in a unit matrix to 0 whereas a shift matrix is a matrix obtained by carrying out a cyclic shift operation on a unit matrix or a semi unit matrix. With the component matrix expressed in the form of a sum matrix as described above, decoding intermediate results (decoding intermediate results obtained in the course of a process to decode messages corresponding to edges corresponding to matrix elements set at 1 in the unit matrix, the semi unit matrix and the shift matrix) corresponding to matrix elements set at 1 in the unit matrix having a weight of 1, the semi unit matrix having a weight of 1 and the shift matrix having a weight of 1 are stored at the same address.
By the same token, decoding intermediate results D412 corresponding to matrix elements set at 1 on the twenty-fifth to thirtieth rows of the parity check matrix H shown in FIG. 16 are stored at nineteenth to twenty-seventh addresses in the decoding intermediate result storage RAM 502. That is to say, the number of words of the decoding intermediate result storage RAM 502 is 27.
On the other hand, at first to ninth addresses in the decoding intermediate result storage RAM 503, decoding intermediate results D412 (D502) corresponding to matrix elements set at 1 on the seventh to twelfth rows of the parity check matrix H shown in FIG. 16 are stored in a form of packing (ignoring matrix elements reset to 0) decoding intermediate results D412 corresponding to matrix elements set at 1 on the rows in the horizontal direction (or the column arrangement direction).
To be more specific, a first shift matrix of a sum matrix (the sum of the first shift matrix obtained by carrying out a cyclic shift operation on a 6×6 unit matrix by 2 matrix elements in the direction to the right and a second shift matrix obtained by carrying out a cyclic shift operation on a 6×6 unit matrix by 4 matrix elements in the direction to the right) included in the parity check matrix H as a component matrix spread throughout a matrix area ranging over intersections (7, 1) to (12, 6) are stored at the first address in the decoding intermediate result storage RAM 503. By the same token, a second shift matrix of the sum matrix included in the parity check matrix H as a component matrix spread throughout a matrix area ranging over intersections (7, 1) to (12, 6) are stored in the second address. Thereafter, in the same way, component matrixes included in the parity check matrix H are stored at the third to ninth addresses.
By the same token, at tenth to eighteenth addresses in the decoding intermediate result storage RAM 503, decoding intermediate results D412 (D502) corresponding to matrix elements set at 1 on the nineteenth to twenty-fourth rows of the parity check matrix H shown in FIG. 16 are stored. In the same way, at nineteenth to twenty-seventh addresses in the decoding intermediate result storage RAM 503, decoding intermediate results D412 (D502) corresponding to matrix elements set at 1 on the thirty-first to thirty-sixth rows of the parity check matrix H shown in FIG. 16 are stored. That is to say, the number of words of the decoding intermediate result storage RAM 503 is 27.
As described above, the number of words in the decoding intermediate result storage RAM 502 and the number of words in the decoding intermediate result storage RAM 503 are each 27. This number is obtained as follows. The row weight of the parity check matrix H is 9. This row weight of 9 is multiplied by the row count of 36 to give a product, which is equal to the number of matrix elements set at 1 in the parity check matrix H. The product is then divided by the number of decoding intermediate results to give a quotient. The number of decoding intermediate results is the number of decoding intermediate results that can be read out from the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503 at the same time. In this case, the number of decoding intermediate results D501, which can be read out from the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503 respectively at the same time, is 6. Finally, the quotient is further divided by the number of RAMs employed in decoding intermediate result storage memory 413 to result in the number 27. In this case, the number of RAMs employed in decoding intermediate result storage memory 413 is 2.
The following description explains details of operations carried out by sections employed in the decoding intermediate result storage memory 413 shown in FIG. 20.
In the decoding intermediate result storage memory 413, when the first computation process carried out by the computation section 412, the decoding intermediate results D412 (uj) of the first computation process carried out by the computation section 412 are provided and the intermediate results D412 is written to predetermined address in either of the decoding intermediate result storage RAM 502 and the decoding intermediate result storage RAM 503. At the same time, decoding intermediate results D412 (uj) of the first computation process carried out by the computation section 412 are read out from the other one of the decoding intermediate result storage RAM 502 and the decoding intermediate result storage RAM 503 and outputted to the computation section 412. When the computation section 415 carries out the second computation process, on the other hand, the decoding intermediate result storage memory 413 is not used for writing the decoding intermediate results of the second computation process in the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503. Instead, the decoding intermediate result storage memory 413 reads out decoding intermediate results from a predetermined address in either the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503 and supplies the decoding intermediate results to the cyclic shift circuit 414.
The switch 501 receives six decoding intermediate results D412 from the computation section 412 and a control signal D4201 as a signal for selecting either the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503 as a memory to be used for storing the decoding intermediate results D412. On the basis of the control signal D4201, the switch 501 selects either the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503 and supplies the six decoding intermediate results D412 to the selected one of the decoding intermediate result storage RAM 502 and the decoding intermediate result storage RAM 503.
Thus, the decoding intermediate result storage RAM 502 may receive the six decoding intermediate results D412 from the switch 501 as decoding intermediate results D501. In this case, the decoding intermediate result storage RAM 502 also receives a control signal D4202 representing an address from the control section 417. In addition, six decoding intermediate results D501 already stored at the address represented by the control signal D4202 as a result of the first computation process carried out previously by the computation section 412 are read out from the address and supplied to a switch 504 as decoding intermediate results D503. Furthermore, the six decoding intermediate results D412 received from the switch 501 as decoding intermediate results D501 are stored (written) at the address represented by the control signal D4202.
As an alternative, the decoding intermediate result storage RAM 503 receives the six decoding intermediate results D412 from the switch 501 as decoding intermediate results D502. In this case, the decoding intermediate result storage RAM 503 also receives a control signal D4203 representing an address from the control section 417. In addition, six decoding intermediate results D502 already stored at the address as a result of the first computation process carried out previously by the computation section 412 are read out from the address and supplied to the switch 504 as decoding intermediate results D504. Furthermore, the six decoding intermediate results D502 received from the switch 501 are stored (written) at the address represented by the control signal D4203.
The switch 504 receives the decoding intermediate results D503 from the decoding intermediate result storage RAM 502 or the decoding intermediate results D504 from the decoding intermediate result storage RAM 503. In addition, the switch 504 also receives a control signal D4204 generated by the control section 417 as a signal for selecting either the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503. On the basis of the control signal D4204, the switch 504 selects either the decoding intermediate result storage RAM 502 or the decoding intermediate result storage RAM 503 as a source for the decoding intermediate results D413 to be output by the switch 504. The switch 504 then passes on the six decoding intermediate results received from the selected one of the decoding intermediate result storage RAM 502 and the decoding intermediate result storage RAM 503 to the computation section 412 and the cyclic shift circuit 414 as the six decoding intermediate results D413.
FIG. 21 shows timing charts used for explaining read and write operations carried out on the decoding intermediate result storage RAM 502 and the decoding intermediate result storage RAM 503, which are employed in the decoding intermediate result storage memory 413.
It is to be noted that, in the timing charts shown in FIG. 21, the horizontal axis represents the lapse of time (t). Notation Ri denotes an operation to read out data corresponding to a matrix element indicated by the suffix i enclosed in a circle in a component matrix shown in FIG. 22 to indicate that the matrix element is a matrix element set at 1. By the same token, notation Wi denotes an operation to write (store) data corresponding to a matrix element indicated by the suffix i enclosed in a circle in a component matrix shown in FIG. 22 to indicate that the matrix element is a matrix element set at 1.
When the computation section 412 carries out the first computation process, six decoding intermediate results D501 per clock are read out for nine consecutive (9 clocks) in respectively (R0 to R8 shown in the figure) on the basis of the control signal D4202 from the same address in the decoding intermediate result storage RAM 502 employed in the decoding intermediate result storage memory 413. The decoding intermediate results D501 corresponding to matrix elements set at 1 on the first to sixth rows of the parity check matrix H are a part of decoding intermediate results D501 already stored in the decoding intermediate result storage RAM 502 as a result of the first computation process carried out previously by the computation section 412. The decoding intermediate results D501 read out from the decoding intermediate result storage RAM 502 are supplied to the computation section 412 by way of the switch 504. That is, since the row weight of the parity check matrix H shown in FIG. 16 is 9, the number of decoding intermediate results D501 corresponding to matrix elements set at 1 on each of the first to sixth rows of the parity check matrix H is 9. Since six decoding intermediate results D501 are corresponding to matrix elements set at 1 on the first to sixth rows of the parity check matrix H are read out from the decoding intermediate result storage RAM 502 in nine consecutive.
Then, six decoding intermediate results D502 per clock are read out for 9 clocks in respectively read operations R9 to R17 shown in the figure on the basis of the control signal D4203 from the same address in the decoding intermediate result storage RAM 503. The decoding intermediate results D502 corresponding to matrix elements set at 1 on the seventh to twelfth rows of the parity check matrix H are a part of decoding intermediate results D501 already stored in the decoding intermediate result storage RAM 503 as a result of the first computation process carried out previously by the computation section 412. The decoding intermediate results D502 read out from the decoding intermediate result storage RAM 503 are supplied to the computation section 412 by way of the switch 504.
The computers 4121 to 4126 and 4151 to 4156 each used for computing a message for a node cause a delay corresponding to a node degree. For example, the computers 4121 to 4126 cause a delay equal to a period of 9 clocks. In addition, if the decoding apparatus 400 carries out a high-speed operation at an operation speed higher than a frequency of 100 MHz, the computers 4121 to 4126 cause a further delay equal to a period of 3 clocks. Thus, pipelining of a period of 3 clocks is required.
That is to say, a time period T1 required by the computation section 412 to complete the first computation process is a period of 12 clocks. The time period T1 is defined as a period from the start of an operation to read out decoding intermediate results D413 from the decoding intermediate result storage memory 413 to the start of an operation to supply decoding intermediate results D412 to the decoding intermediate result storage memory 413 as a result of the first computation process carried out on the decoding intermediate results D413.
Thus, as the time period T1 lapses since the first read operation (R0) to read out decoding intermediate results D503 from the decoding intermediate result storage RAM 502, the computation section 412 starts an operation to supply six decoding intermediate results D412 corresponding to matrix elements set at 1 on respectively the first to sixth rows of the parity check matrix H to the decoding intermediate result storage memory 413 as a result of the first computation process. In the decoding intermediate result storage memory 413, the decoding intermediate results D413 are supplied to the decoding intermediate result storage RAM 502 by way of the switch 501 as decoding intermediate results D501. In the decoding intermediate result storage RAM 502, the decoding intermediate results D501 are stored at an address used for storing decoding intermediate results D503 in nine consecutive store operations (W0 to W8) on the basis of the control signal D4202.
That is to say, a wait time is needed for 3 clocks time period Tw (=T1−9). The time period Tw is a period from the end of the nine consecutive read operations (R0 to R8) to read out decoding intermediate results D503 from the decoding intermediate result storage RAM 502 to the start of the nine consecutive store operations (W0 to W8) to store decoding intermediate results D501 in the decoding intermediate result storage RAM 502.
In other words, the nine consecutive store operations (W0 to W8) to store in the decoding intermediate result storage RAM 502 ends after the time period Tw lapses after the end of the nine consecutive read operations (R9 to R17) to read out from the decoding intermediate result storage RAM 503. That is to say, the time period Tw is required as a period between the end of nine consecutive read operations (R9 to R17) to read out from the decoding intermediate result storage RAM 503 and the start of nine consecutive read operations (R18 to R26) to read out from the decoding intermediate result storage RAM 502.
In addition, there have also been proposed some methods including a method implemented by approximation the sum product algorithm cited before. However, these proposed methods lead to deterioration of performance.
In the case of the aforementioned sum product algorithm that is implemented by hardware, as described above, the processing to compute messages each corresponding to an edge (the check-node process, the variable-node process, the first computation process and the second computation process) can be carried out by adoption of a serial method which, processes of the processing are carried out sequentially one process after another; a full parallel method which, all processes of the processing are carried out concurrently at the same time; or a parallel method which, some processes of the processing are carried out concurrently at one time in an operation.
In the case of the full parallel method or the parallel method for carrying out P processes concurrently at one time, however, a large value of P undesirably entails an increased circuit scale of the computation section 412 in particular. In the case of a P value of and a code length of 64,800 for example, the circuit scale of the computation section 412 may reach 20% of the entire decoding apparatus 400 or 60% of the logic circuit excluding memories (for example, the decoding intermediate result storage memory 410, the decoding intermediate result storage memory 413 and the reception memory 416) employed in the decoding apparatus 400 in some cases.
In addition, time periods Tw are required as shown in FIG. 21 as periods during which no data is read out from the decoding intermediate result storage RAM 502 and the decoding intermediate result storage RAM 503. That is to say, during a time period Tw, no decoding intermediate results D413 are supplied to the computation section 412 for carrying out the first computation process. Thus, during a time period Tw, the computation section 412 is undesirably in an idle state of carrying out no first computation process. In the case of a low node degree particularly, the time period Tw becomes relatively long, putting the computation section 412 in a long wasteful period of time.
[Non-Patent Document 1]
C. Howland and A. Blanksby, “Parallel Decoding Architectures for Low Density Parity Check Codes”, Symposium on Circuits and Systems, 2001
[Non-Patent Document 2]
E. Yeo, P. Pakzad, B. Nikolic and V. Anantharam, “VLSI Architectures for iterative Decoders in Magnetic Recording Channels”, IEEE Transactions on Magnetics, Vol. 37, No. 2, March 2001
[Non-Patent Document 3]
T. Zhang, K. K. Parhi, “Joint (3, k)-regular LDPC Code and decoder/encoder design,” IEEE Transactions on Signal Processing, Vol. 52, No. 4, pp. 1065 to 1079, April 2004
[Non-Patent Document 4]
M. M. Mansour, N. R. Shanbhag, “A novel design methodology for high-performance programmable decoder cores for AA-LDPC codes,” Proceedings of IEEE Workshop on Signal Processing Systems 2003 (SIPS 2003), pp. 29 to 34, August 2003
[Patent Document 1]
Japanese Patent Laid-open No. 2004-364233